class Solution:
    def minimumSubstringsInPartition(self, s: str) -> int:
        @cache
        def dfs(i):
            if i < 0:
                return 0
            res = inf
            cnt = defaultdict(int)
            max_cnt = 0
            for j in range(i, -1, -1):
                cnt[s[j]] += 1
                max_cnt = max(max_cnt, cnt[s[j]])
                if i-j+1 == len(cnt) * max_cnt:
                    res = min(res, dfs(j-1)+1)
            return res
        return dfs(len(s)-1)
    
    def minimumSubstringsInPartition2(self, s: str) -> int:
        n = len(s)
        dp = [0] + [inf]*n
        for i in range(1, n+1):
            cnt = defaultdict(int)
            max_cnt = 0
            for j in range(i-1, -1, -1):
                cnt[s[j]] += 1
                max_cnt = max(max_cnt, cnt[s[j]])
                if len(cnt)*max_cnt == i-j+1:
                    dp[i] = min(dp[i], dp[j-1]+1)
        return dp[n]